package Others;

public class _427_ConstructQuadTree {
    public Node construct(int[][] grid) {
        return build(0, 0, grid.length - 1, grid[0].length - 1,grid);
    }

    public Node build(int r1, int c1, int r2, int c2, int[][] g) {
        if(r1>r2 || c1>c2) return null;
        boolean isLeaf = true;
        int val = g[r1][c1];
        for (int i = r1; i <= r2; i++) {
            for (int j = c1; j <= c2; j++) {
                if (g[i][j] != val) {
                    isLeaf = false;
                    break;
                }
            }
        }
        if (isLeaf) {
            return new Node(val == 1, true, null, null, null, null);
        }
        int rowMid = (r1 + r2) / 2;
        int colMid = (c1 + c2) / 2;
        return new Node(false, false,
                build(r1, c1, rowMid, colMid, g),
                build(r1, colMid + 1, rowMid, c2, g),
                build(rowMid + 1,c1, r2, colMid,g),
                build(rowMid + 1, colMid + 1, r2, c2,g));

    }

}
